package bm2;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/7/19 22:51
 * BM2.链表内指定区间反转
 * https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&tqId=654&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    // 头插法
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // 构造哑巴节点, 最后返回的结果为 muteNode.next
        ListNode muteNode = new ListNode(-1);
        muteNode.next = head;
        // 计算需要反转的节点的个数
        int nodeCount = n - m + 1;
        // 定义辅助指针
        ListNode pre = muteNode;
        ListNode cur = pre.next;
        // 先找到需要反转区间最左节点的前一个节点 pre
        while (--m != 0) {
            pre = pre.next;
            cur = cur.next;
        }
        // 将 pre 看作头节点, 将 pre 后的 nodeCount 个节点以头插的方式进行反转
        pre.next = null;
        ListNode temp = cur; // 记录反转部分的起始节点, 同时也是反转区间的尾巴节点
        // 头插法
        while (nodeCount-- != 0) {
            ListNode curNext = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            cur = curNext;
        }
        // 将后面的部分连起来
        temp.next = cur;
        // 返回结果
        return muteNode.next;
    }


    private static class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
}
